package tree

type BsTree struct {
	Root *BTreeNode
}

func NewBSTree(root *BTreeNode) (bst *BsTree) {
	bst = &BsTree{Root: root}
	return bst
}

//二叉搜索树.从根开始对比.小往左,大往右(相等在node上数量),一直到最下层
func (bst *BsTree) Insert(val int) {
	p := bst.Root
	if p == nil {
		bst.Root = &BTreeNode{Data: val}
		return
	}

	for {
		pval, err := p.Data.(int)
		if !err {
			panic("convert int err")
		}
		if val < pval {
			if p.LeftChild != nil {
				p = p.LeftChild
				continue
			}
			p.LeftChild = &BTreeNode{Data: val, Parent: p}
			break
		} else if val > pval {
			if p.RightChild != nil {
				p = p.RightChild
				continue
			}
			p.RightChild = &BTreeNode{Data: val, Parent: p}
			break
		}
	}
}
func (bst BsTree) Query(val int) *BTreeNode {
	curr := bst.Root
	for {
		if curr == nil {
			return nil
		}
		currval := curr.Data.(int)
		switch {
		case val == currval:
			return curr
		case val < currval:
			curr = curr.LeftChild
			continue
		case val > currval:
			curr = curr.RightChild
			continue
		}
	}
}

//删除三种情况
//1 叶子节点直接删除
// 2 被删除的节点只有左忆节点或右子节点,删除节点后,将子节点的父节点链接到被删节点的父节点
// 3 被删除节点左右都有节点,则在删除节点后,在右子树中找最小的节点放到被删除节点位置
func (bst *BsTree) Del(val int) {
	if bst.Root != nil {
		node := bst.Query(val)
		if node == nil {
			return
		}
		if node.RightChild == nil && node.LeftChild == nil {
			bst.delLeaf(node)
		} else if node.RightChild == nil {
			bst.delOnlyLeft(node)
		} else if node.LeftChild == nil {
			bst.delOnlyRight(node)
		} else {
			bst.delFull(node)
		}
	}

}

//删除叶子节点
func (bst *BsTree) delLeaf(node *BTreeNode) {
	if node.Parent == nil {
		bst.Root = nil
	}
	if node.Parent.RightChild == node {
		node.Parent.RightChild = nil
	}
	if node.Parent.LeftChild == node {
		node.Parent.LeftChild = nil
	}
	node.Parent = nil
}
func (bst *BsTree) delOnlyRight(node *BTreeNode) {
	if node.Parent == nil {
		bst.Root = node.RightChild
		node.RightChild.Parent = nil
	} else if node.Parent.LeftChild != node {
		node.Parent.LeftChild = node.RightChild
		node.RightChild.Parent = node.Parent
	} else {
		node.Parent.RightChild = node.RightChild
		node.RightChild.Parent = node.Parent
	}
}
func (bst *BsTree) delOnlyLeft(node *BTreeNode) {
	if node.Parent == nil {
		node.LeftChild.Parent = nil
		bst.Root = node.LeftChild
	} else if node.Parent.LeftChild != node {
		node.Parent.LeftChild = node.LeftChild
		node.LeftChild.Parent = node.Parent
	} else {
		node.Parent.RightChild = node.LeftChild
		node.LeftChild.Parent = node.Parent
	}
}
func (bst *BsTree) delFull(node *BTreeNode) {
	p := node.RightChild
	for p.LeftChild != nil {
		p = p.LeftChild
	}
	node.Data = p.Data
	if p.RightChild != nil {
		bst.delOnlyRight(p)
	} else {
		bst.delLeaf(p)
	}

}
